/**
 * 普通二维背包解题思路
 * 
 * f[i][j] 表示只看前i个物品,总体积是j的情况下,总价值最大是多少
 * w[i] 表示第i个物品的体积(容量) v[i]表示第i个物品的价值
 * 
 * result = max{f[n][0~V]}
 * 
 * f[i][j]有两种情况:
 *      1.不选第i个物品 f[i][j] = f[i-1][j];//其价值就是i之前的物品价值
 *      2.选第i个物品,f[i][j] = f[i-1][j-w[i]]+v[i];
 * f[i][j] = max [1.,2.]
 * f[0][0] = 0;//什么也不选的时候,价值为0
 * 
 * 时间复杂度:n*m
 */

/**
 * 
 * @param {Array} w 物体体积数组
 * @param {Array} v 物品价值数组
 * @param {Number} m 最大体积数
 */
 function knapSack(w,v,m) {

    let size =  v.length;
    //总价值
    let dp = arrayInit(size,m+1);

    //1.初始化第一行
     //仅考虑容量为C的背包放第0个物品的情况
     for (let i = 0; i <= m; i++) {
        dp[0][i] = w[0] <= i ? v[0] : 0;
    }

    //2.计算其他列
    for (let i = 1 ;i < size; i++) {
        for (let j = 0; j <= m; j++) {
               //2.1当不放入第i个物品时
               dp[i][j] = dp[i-1][j];
               if(j >= v[i]){
                   //2.2如果背包容量小于物品体积
                   dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i])
               }     
        }
    }
    return dp[size - 1][m];
 }

 function max(n1,n2) {
     return n1-n2>=0 ? n1:n2;
 }

 function arrayInit(n,m) {
     //总价值
    let dp = new Array();
    //初始化二维数组
    for (let i = 0; i < n; i++) {
        dp[i]  = new Array();//声明二维数组
       for (let j = 0; j < m; j++) {
           dp[i][j] = '';
       }    
    }
    return dp;
 }
 // [2,3,4,5] 体积
 // [3,4,5,6] 价值
 console.log(knapSack([2,3,4,5],[3,4,5,6],8));